In this paper we consider the problem of segmenting $n$ aligned randomsequences of equal length $m$, into a finite number of independent blocks. Wepropose to use a penalized maximum likelihood criterion to infer simultaneouslythe number of points of independence as well as the position of each one ofthese points. We show how to compute the estimator efficiently by means of adynamic programming algorithm with time complexity $O(m^2n)$. We also proposeanother algorithm, called hierarchical algorithm, that provides anapproximation to the estimator when the sample size increases and runs in time$O(mn)$. Our main theoretical result is the proof of almost sure consistency ofthe estimator and the convergence of the hierarchical algorithm when the samplesize $n$ grows to infinity. We illustrate the convergence of these algorithmsthrough some simulation examples and we apply the method to a real proteinsequence alignment of Ebola Virus.
展开▼
机译：在本文中，我们考虑将等长$ m $的对齐对齐的n个序列随机分成有限数量的独立块的问题。我们建议使用惩罚最大似然准则来同时推断独立点的数量以及每个这些点的位置。我们展示了如何通过具有时间复杂度$ O（m ^ 2n）$的动态规划算法来有效地计算估计量。我们还提出了另一种算法，称为分层算法，当样本量增加并在时间$ O（mn）$中运行时，该算法为估计量提供近似值。我们的主要理论结果是证明，当样本量$ n $增长到无穷大时，估计量的一致性和分层算法的收敛性几乎可以肯定。我们通过一些仿真示例说明了这些算法的收敛性，并将该方法应用于埃博拉病毒的真实蛋白质序列比对。
展开▼
